В черный ящик
кладутся листки с написанными на них числами. На каждом листке – ровно одно
целое число. Иногда некоторые листки исчезают из ящика. После каждого события
(когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести
число, которое встречается чаще всего на листках, находящихся в данный момент в
ящике. Если таких чисел несколько, выведите наименьшее.
Вход. Первая строка содержит количество событий n (1 ≤ n ≤ 2*105). Каждая из следующих n строк содержит описание одного
события:
+ x – положен листок с числом x (1 ≤ x ≤ 106);
- x – исчез листок с числом x
(гарантируется, что в ящике был хотя бы один листок с числом x).
Выход. Вывести в точности n
строк – по одной для
каждого события. Каждая строка должна содержать одно число – ответ к задаче. Если после какого-то события
ящик оказался пуст, следует вывести 0.
|
Пример
входа |
Пример
выхода |
|
3 + 1 - 1 + 2 |
1 0 2 |
РЕШЕНИЕ
дерево отрезков
Пусть a0, a1,
…, a1000000 – массив чисел,
изначально заполненный нулями. При выполнении события + x будем совершать a[x]++. При выполнении события - x будем совершать a[x]--. Тогда число, чаще всего
встречающееся на листках, и есть максимум на интервале [0; 106].
Таким образом
достаточно моделировать операции с массивом при помощи дерева отрезков,
поддерживающего максимум.
Объявим дерево
отрезков.
#define MAX 1000001
struct node
{
int x, frequency;
}
SegmentTree[4*MAX];
Сравнение элементов.
struct node max(node a, node b)
{
if (a.frequency > b.frequency) return a;
if ((a.frequency == b.frequency) && (a.x <
b.x)) return a;
return b;
}
Построение дерева отрезков.
void BuildTree(int Vertex, int Left, int Right)
{
if (Left == Right)
{
SegmentTree[Vertex].x = Left;
SegmentTree[Vertex].frequency = 0;
}
else
{
int Middle = (Left + Right) / 2;
BuildTree(2*Vertex, Left, Middle);
BuildTree(2*Vertex+1, Middle+1, Right);
SegmentTree[Vertex] =
max(SegmentTree[2*Vertex],SegmentTree[2*Vertex+1]);
}
}
Прибавление a[Position]
+= Value.
void Add(int Vertex, int LeftPos, int
RightPos,
int Position, int
Value)
{
if (LeftPos == RightPos)
SegmentTree[Vertex].frequency += Value;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
Add(2*Vertex, LeftPos, Middle, Position, Value);
else
Add(2*Vertex+1, Middle+1, RightPos, Position, Value);
SegmentTree[Vertex] =
max(SegmentTree[2*Vertex],SegmentTree[2*Vertex+1]);
}
}
Основная часть программы. Строим дерево отрезков.
scanf("%d\n",&n);
BuildTree(1, 0, MAX - 1);
Последовательно обрабатываем запросы.
while(n--)
{
scanf("%c %d\n",&c,&x);
if (c == '+')
Add(1,0,MAX-1,x,1);
else Add(1,0,MAX-1,x,-1);
printf("%d\n",SegmentTree[1].x);
}